package leetcode;

import java.util.*;

/**
 * Created by tiang on 2018/9/6.
 * Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

 Your algorithm should run in O(n) complexity.

 Example:

 Input: [100, 4, 200, 1, 3, 2]
 Output: 4
 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
 就是求这个序列中能合并成一个连续序列的最大长度
 */
public class LongestConsecutiveSequence {
    static class Node{
        private int start, end;
        public Node(int s, int e){
            this.start = s;
            this.end = e;
        }
    }

    /**
     * 基本上算是暴力破解了
     * @param nums 数组
     * @return 连续序列长度
     */
    public int longestConsecutive(int[] nums) {
        HashSet<Node> set = new HashSet<>();
        for (int num : nums) {
            HashSet<Node> temp = new HashSet<>();
            for (Node n : set) {
                if (n.start <= num && n.end >= num)
                    break;
                else if (n.start == num + 1 || n.end == num - 1) {
                    temp.add(n);
                }
            }

            Node nt = new Node(num, num);
            for (Node n : temp) {
                if (nt.start >= n.start)
                    nt.start = n.start;
                if (nt.end <= n.end)
                    nt.end = n.end;
            }
            Iterator<Node> it = set.iterator();
            while (it.hasNext()) {
                Node n = it.next();
                if (temp.contains(n))
                    it.remove();
            }
            set.add(nt);

        }
        int result = 0;
        for (Node n : set) {
            if (n.end - n.start + 1 > result)
                result = n.end - n.start + 1;
        }
        return result;
    }

    public int longestConsecutiveNew(int[] nums){
        // 存储i位置所在段的最大长度，但是只有处于段边界位置的才是正确的，段中位置的可能不正确
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for(int num : nums){
            // 如果当前map中已经存在了元素，已经存在的元素是不会影响段的重新组合的，所以直接忽略
            if(map.containsKey(num))
                continue;
            // 当前元素的上一个元素所在段的长度
            int left = map.get(num-1) == null ? 0:map.get(num-1);
            // 当前元素的下一个元素所在段的长度
            int right = map.get(num+1) == null ?  0:map.get(num+1);
            // 当前元素加入之后，左右两个段合并
            int value = left+right+1;
            // 计算最大结果
            res = Integer.max(res, value);
            // 插入当前元素，主要是避免以后会出现相同的元素进入
            map.put(num, value);
            // 更新新的段的左右两端的值
            map.put(num-left, value);
            map.put(num+right, value);
        }
        return res;
    }
}
